package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/10 9:30
 * @description：https://leetcode-cn.com/problems/shortest-completing-word/
 */
public class 最短补全词 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.shortestCompletingWord("1s3 PSt",
                new String[]{"step", "steps", "stripe", "stepple"}));
    }

    class Solution {
        public String shortestCompletingWord(String licensePlate, String[] words) {
            int[] counts = new int[26];
            int sum = 0;
            for (char c : licensePlate.toLowerCase().toCharArray()) {
                if (Character.isLowerCase(c)) {
                    counts[c - 'a']++;
                    sum++;
                }
            }
            Arrays.sort(words, Comparator.comparingInt(String::length));
            for (String word : words) {
                int sum_ = 0;
                int[] curCounts = Arrays.copyOf(counts, counts.length);
                for (char c : word.toCharArray()) {
                    if (curCounts[c - 'a'] > 0) {
                        curCounts[c - 'a']--;
                        sum_++;
                    }
                    if (sum_ == sum) return word;
                }
            }
            return null;
        }
    }
}
